GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>AC-3-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">AC-3-Algorithmus</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>AC-3-Algorithmus</b> (von <span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic"><i>arc consistency algorithm</i></span>, dt.: Kantenkonsistenz-Algorithmus) ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zur Lösung von <a href="Constraint-Satisfaction-Problem" title="Constraint-Satisfaction-Problem">Constraint-Erfüllungsproblemen</a> (CSPs) mit binären Bedingungen. Er wurde 1977 von Alan Mackworth entwickelt<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Der_Algorithmus">Der Algorithmus</h2></div>

<p>AC-3 arbeitet auf den Domänen von Variablen in Constraint-Erfüllungsproblemen. Eine <i>Variable</i> kann hier jeden Wert einer festgelegten Menge, ihrer <i>Domäne</i>, annehmen. Diese Belegungen der Variablen werden durch klar definierte Regeln (<i>Constraints</i>) eingeschränkt. Diese Constraints können die Belegungen anderer Variablen beinhalten.

</p><p>Ein CSP kann als gerichteter Graph betrachtet werden, wobei die Knoten den Variablen des Problems entsprechen und die Kanten für Constraints stehen. AC-3 untersucht die Kanten zwischen Variablen-Paaren (<i>x</i>, <i>y</i>). Es werden jene Werte aus den Domänen von <i>x</i> und <i>y</i> entfernt, die nicht mit den Constraints zwischen <i>x</i> und <i>y</i> konsistent sind. Der Algorithmus speichert die Kanten, die noch geprüft werden müssen. Wenn Werte aus der Domäne einer Variable entfernt werden, werden alle Kanten (Constraints) an dieser Variable der Menge der noch zu prüfenden Kanten hinzugefügt. Da die Domänen von Variablen endlich sind – und in jedem Schritt entweder eine Kante oder eine Variable entfernt werden – terminiert der Algorithmus garantiert.

</p><p>Ein Beispiel anhand eines einfachen Problems:

Es sei eine Variable <i>X</i> mit der Domäne D(<i>X</i>) = {0, 1, 2, 3, 4, 5} gegeben. Außerdem sei eine Variable <i>Y</i> mit D(<i>Y</i>) = {0, 1, 2, 3, 4, 5} gegeben. Die Constraints seien <i>C1</i> = „<i>X</i> sei gerade“ und <i>C2</i> = „<i>X</i> + <i>Y</i> = 4“. Da AC-3 in einem gerichteten Graphen repräsentiert wird, existieren dabei aufgrund von <i>C2</i> zwei Kanten zwischen <i>X</i> und <i>Y</i>.

</p><p>Bei Anwendung von AC-3 werden zunächst die ungeraden Werte der Domäne von <i>X</i> entfernt, wodurch alle verbleibenden Belegungsmöglichkeiten für <i>X</i> (D(<i>X</i>) = { 0, 2, 4 }) den Constraint <i>C1</i> erfüllen. Anschließend werden die Kanten zwischen <i>X</i> und <i>Y</i> untersucht. Constraint <i>C2</i> wird nur durch die Belegungen (<i>X</i>=0, <i>Y</i>=4), (<i>X</i>=2, <i>Y</i>=2), und (<i>X</i>=4, <i>Y</i>=0) erfüllt. AC-3 terminiert mit D(<i>X</i>) = {0, 2, 4} und D(<i>Y</i>) = {0, 2, 4}.

</p><p>AC-3 in Pseudocode:

</p>

<pre><b>function AC3</b>

<i>// Reduziert Domänen</i>

<b>queue</b> = Alle Kanten des CSP

<b>while</b> (!empty(queue))

<b>Entferne</b> eine Kante (x, y) aus <b>queue</b>;

<b>if</b>(EntferneInkonsistenteWerte(x, y))

<b>foreach</b> (Nachbar z von x)

queue.ADD(Kante(z, x))

<b>function AC3 end</b>

</pre>

<pre><b>function EntferneInkonsistenteWerte(x, y)</b>

<i>// Liefert true, wenn Domäne D(x) reduziert wird</i>

<b>removed</b> = false

<b>foreach</b> (Value v1 in D(x))

<b>if</b>(Kein v2 in D(Y), so dass (x=v1, y=v2) alle Constraints zwischen (x,y) erfüllt)

D(x).LÖSCHE(v1)

removed = true

return <b>removed</b>

<b>function EntferneInkonsistenteWerte end</b>

</pre>

<p>Der Algorithmus hat eine Worst-Case-Zeit-Komplexität von <b>O</b>(<i>ed<sup>3</sup></i>), Worst-Case-Speicher-Komplexität: <b>O</b>(<i>e</i>), wobei <i>e</i> die Anzahl der Kanten und <i>d</i> die Größe der größten Domäne ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Belege">Belege</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Alan K. Mackworth: <i>Consistency in Networks of Relations.</i> In: <i>Artificial Intelligence.</i> Bd. 8, Nr. 1, Februar 1977, <span class="-print"><a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220004-3702%22&key=cql">0004-3702</a></span></span>, S. 99–118, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1016/0004-3702%2877%2990007-8">10.1016/0004-3702(77)90007-8</a></span>.</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2022-08-24" href="https://de.wikipedia.org/wiki/?title=AC-3-Algorithmus&oldid=225609608">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>